//表达式意义:dist[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离
//递推公式:dist[i, j, k] = min(dist[i, j, k - 1), dist[i, k, k - 1] + dist[k, j, k - 1]//前面决定不加入k点，后面决定加入
//既每次一k要加一的时候，每一条路径都要决定，他们直接的最短路径需不需要经过k点
#include <iostream>
using namespace std;

const int N = 210;
const int INF = 0x3f3f3f3f;
int d[N][N][N];       //递推公式
int n, m, k, a, b, c; //接受输入

void floyd() //弗洛伊德算法
{
    for (int k = 1; k <= n; ++k)                                                   //从1开始(0)已经确定了，更新第三维的下标
        for (int i = 1; i <= n; ++i)                                               //更新第二维的下标
            for (int j = 1; j <= n; ++j)                                           //更新第一维的下标
                d[i][j][k] = min(d[i][j][k - 1], d[i][k][k - 1] + d[k][j][k - 1]); //递推公式
    return;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j)
                d[i][j][0] = 0; //我到我自己的距离为0，而且图中不需要经过
            else
                d[i][j][0] = INF; //到其他点的距离先初始化为无穷大，先默认可以一步到位，所以第三维等于0
                                  //以上初始化完成以后，就得到了一个各个点相互独立，互不相干的图
    while (m--)
    {
        cin >> a >> b >> c;
        d[a][b][0] = min(c, d[a][b][0]); //再通过输入将默认的无链接的图通过输入给的信息连接起来
    }
    floyd();
    while (k--)
    {
        cin >> a >> b;
        if (d[a][b][n] > INF / 2)
            cout << "impossible" << endl;
        else
            cout << d[a][b][n] << endl;
    }
    return 0;
}